// async:对于一些分布的单任务多CPU计算的任务,创建一个线程或者线程池还需要去销毁.可能的开销会存在
// 对于async而言,其可以自己创建一个线程,通过future来接收,其任务就被异步处理,在外部get或者wait获取

#include <stdlib.h>
#include <time.h>

#include <algorithm>
#include <future>
#include <iostream>
#include <list>

// 1.单线程串行快速排列
template <class T>
void quick_sort_recursive(T arr[], int l, int r) {
    if (l >= r) return;
    T key = arr[l + rand() % (r - l + 1)];
    int left = l - 1, right = r + 1;
    int pos = l;
    while (pos < right) {
        if (arr[pos] < key)
            std::swap(arr[pos++], arr[++left]);
        else if (arr[pos] > key)
            std::swap(arr[pos], arr[--right]);
        else
            pos++;
    }
    //[l,left] [left+1,right-1] [right,r]
    quick_sort_recursive(arr, l, left);
    quick_sort_recursive(arr, right, r);
}

void qsort_r() {
    srand(time(NULL));
    int arr[10] = {7, 5, 6, 1, 2, 9, 3, 8, 4, 0};
    for (int i = 0; i < 10; i++) std::cout << arr[i] << " ";
    std::cout << std::endl;
    quick_sort_recursive(arr, 0, (sizeof(arr) / sizeof(int) - 1));
    for (int i = 0; i < 10; i++) std::cout << arr[i] << " ";
    std::cout << std::endl;
}

// 2.函数式编程
/*
目前理解到的:只关注做什么而不是怎么做,给与一个容器一个中间的状态就不在乎外部怎么样了
*/
template <typename T>
std::list<T> sequential_quick_sort(std::list<T> input) {
    if (input.empty()) {
        return input;
    }
    std::list<T> result;
    //  ① 将input中的第一个元素放入result中，并且将这第一个元素从input中删除
    result.splice(result.begin(), input, input.begin());
    //  ② 取result的第一个元素，将来用这个元素做切割，切割input中的列表。
    T const& pivot = *result.begin();
    //  ③std::partition
    //  是一个标准库函数，用于将容器或数组中的元素按照指定的条件进行分区，
    // 使得满足条件的元素排在不满足条件的元素之前。
    // 所以经过计算divide_point指向的是input中第一个大于等于pivot的元素
    auto divide_point = std::partition(input.begin(), input.end(),
                                       [&](T const& t) { return t < pivot; });
    // ④ 我们将小于pivot的元素放入lower_part中
    std::list<T> lower_part;
    lower_part.splice(lower_part.end(), input, input.begin(), divide_point);
    // ⑤我们将lower_part传递给sequential_quick_sort
    // 返回一个新的有序的从小到大的序列
    // lower_part 中都是小于divide_point的值
    auto new_lower(sequential_quick_sort(std::move(lower_part)));
    // ⑥我们剩余的input列表传递给sequential_quick_sort递归调用，input中都是大于divide_point的值。
    auto new_higher(sequential_quick_sort(std::move(input)));
    // ⑦到此时new_higher和new_lower都是从小到大排序好的列表
    // 将new_higher 拼接到result的尾部
    result.splice(result.end(), new_higher);
    // 将new_lower 拼接到result的头部
    result.splice(result.begin(), new_lower);
    return result;
}

void test_sequential_quick() {
    std::list<int> numlists = {6, 1, 0, 7, 5, 2, 9, -1};
    auto sort_result = sequential_quick_sort(numlists);
    std::cout << "sorted result is ";
    for (auto iter = sort_result.begin(); iter != sort_result.end(); iter++) {
        std::cout << " " << (*iter);
    }
    std::cout << std::endl;
}

// 并行版本
template <typename T>
std::list<T> parallel_quick_sort(std::list<T> input) {
    if (input.empty()) {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(), input, input.begin());
    T const& pivot = *result.begin();
    auto divide_point = std::partition(input.begin(), input.end(),
                                       [&](T const& t) { return t < pivot; });
    std::list<T> lower_part;
    lower_part.splice(lower_part.end(), input, input.begin(), divide_point);
    // ①因为lower_part是副本，所以并行操作不会引发逻辑错误，这里可以启动future做排序
    std::future<std::list<T>> new_lower(
        std::async(&parallel_quick_sort<T>, std::move(lower_part)));
    // ②
    auto new_higher(parallel_quick_sort(std::move(input)));
    result.splice(result.end(), new_higher);
    result.splice(result.begin(), new_lower.get());
    return result;
}

void test_parallel_sequential_quick() {
    std::list<int> numlists = {6, 1, 0, 7, 5, 2, 9, -1};
    auto sort_result = sequential_quick_sort(numlists);
    std::cout << "sorted result is ";
    for (auto iter = sort_result.begin(); iter != sort_result.end(); iter++) {
        std::cout << " " << (*iter);
    }
    std::cout << std::endl;
}

int main() {
    // qsort_r();
    // test_sequential_quick();
    return 0;
}